#!/usr/bin/env python
# -*- coding: utf-8 -*-

# @Time     :2020/12/02
# @Author   :Changshu
# @File     :Exercise_509.py
# 509. 斐波那契数
# 斐波那契数，通常用 F(n) 表示，形成的序列称为斐波那契数列。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是：
# 0 ≤ N ≤ 30

'''法一，递归
def fib(N: int) -> int:
	if N==0:
		return 0
	if N==1:
		return 1
	return fib(N-1)+fib(N-2)
'''

'''非递归'''
def fib(N: int) -> int:
	r=[0,1]
	for n in range(N-1):
		r.append(r[-1]+r[-2])
	return r[N]

if __name__ == '__main__':
	N=10
	print(fib(N))